import java.util.StringTokenizer;
import java.util.Stack;

public class MyDC {
    private final char ADD = '+';
    private final char SUBTRACT = '-';
    private final char MULTIPLY = '*';
    private final char DIVIDE = '/';
    private final char LPARE = '(';
    private final char RPARE = ')';
    private Stack<Integer> stack;
    private Stack<Character> stacktwo;

    public MyDC() {
        stack = new Stack<Integer> ();
        stacktwo = new Stack<Character>();
    }

    public int evaluate(String expr) {
        int i, result = 0,op1, op2;
        char token[]=expr.toCharArray();
        for(i=0;i<token.length;i++){
            if (isOperator(token[i])) {
                op2 = stack.pop();
                op1 = stack.pop();
                result = evalSingleOp(token[i], op1, op2);
                stack.push(new Integer(result));
            } else{
                stack.push(new Integer(token[i]-'0'));
            }
        }

        return result;
    }

    private boolean isOperator(char token) {
        return (token=='+' || token=='-' ||
                token=='*' || token=='/');
    }

    private int evalSingleOp(char operation, int op1, int op2) {
        int result = 0;

        switch (operation) {
            case ADD:
                result = op1 + op2;
                break;
            case SUBTRACT:
                result = op1 - op2;
                break;
            case MULTIPLY:
                result = op1 * op2;
                break;
            case DIVIDE:
                result = op1 / op2;
        }

        return result;
    }
    public String trans(String before){
        int i,j=0;
        char step[] = before.toCharArray();
        char after[] = new char[step.length];
        for(i=0;i<step.length;i++) {
            if (step[i] >= '0' && step[i] <= '9') {
                after[j] = step[i];
                j++;
                if(i==(step.length)-1){
                    while(stacktwo.empty()==false) {
                        after[j]=stacktwo.pop();
                        j++;
                    }
                }
            }
            else if(stacktwo.empty()||step[i]=='('||stacktwo.peek()=='('||stacktwo.peek()==')') {
                stacktwo.push(new Character(step[i]));
                if(i==(step.length)-1){
                    while(stacktwo.empty()==false) {
                        after[j]=stacktwo.pop();
                        j++;
                    }
                }
            }
            else if(step[i]==')') {
                while (stacktwo.peek() != '(') {
                    after[j] = stacktwo.pop();
                    j++;
                }
                stacktwo.pop();
                if(i==(step.length)-1){
                    while(stacktwo.empty()==false) {
                        after[j]=stacktwo.pop();
                        j++;
                    }
                }
            }
            else {
                switch (step[i]) {
                    case ADD:
                    case SUBTRACT:
                    {
                        while(stacktwo.peek()=='*'||stacktwo.peek()=='/'||stacktwo.peek()=='+'||stacktwo.peek()=='-'){
                            after[j]=stacktwo.pop();
                            j++;
                            if(stacktwo.empty()){
                                break;
                            }
                        }
                        stacktwo.push(new Character(step[i]));
                        break;
                    }
                    case MULTIPLY:
                    case DIVIDE:
                    {
                        while(stacktwo.peek()=='*'||stacktwo.peek()=='/'){
                            after[j]=stacktwo.pop();
                            j++;
                            if(stacktwo.empty()){
                                break;
                            }
                        }
                        stacktwo.push(new Character(step[i]));
                        break;
                    }
                }
                if(i==(step.length)-1){
                    while(stacktwo.empty()!=false) {
                        after[j]=stacktwo.pop();
                        j++;
                    }
                }
            }
        }
        String str = new String(after);
        return str;
    }

}

